package main

import "fmt"

/**
Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false
Example 2:

Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?


不限定空间复杂度的话，可以借助stack或是reverse linked list

限定空间复杂度O(1) 解法

1.寻找中点
2.翻转链表后半部分(此时原链表被拆成中点前链表和中点后翻转链表)
3.步长为1迭代比较前后两链表的值

疑问1 如何寻找中点
通过快慢指针来查找

疑问2 奇数个和偶数个数的链表都可以通过翻转比较来判断么？
假设输入是奇数个，1 2 3 2 1，中点是3，切割后的链表a为123nil 链表b为123nil(后半部分翻转得来)，接着可以继续进行第三步判断没问题
假设输入的是偶数个，1 2 3 3 2 1，中点得出是第四位的3，切割后链表a为1233nil,b为123nil，b链表是原链表后半部分翻转得来，只要依次对比ab链表同位置的值即可(当b链表为nil时停止循环)

*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Forward *ListNode
 * }
 */

type ListNode struct {
	Val  int
	Next *ListNode
}

func main() {
	head := generateListByVals([]int{1, 2, 3, 3, 2, 1})

	fmt.Println(isPalindrome(head))
}
func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	p := findMidNode(head)
	head2 := revertLinkedList(p)
	for ; head != nil && head2 != nil; head, head2 = head.Next, head2.Next { //循环条件head != nil && head2 != nil
		if head.Val != head2.Val {
			return false
		}
	}
	return true
}

func revertLinkedList(node *ListNode) *ListNode {
	if node == nil || node.Next == nil {
		return node
	}

	var prev *ListNode = nil
	for node != nil {
		tmp := node.Next
		node.Next = prev
		prev = node
		node = tmp
	}

	return prev
}

func findMidNode(head *ListNode) *ListNode {
	slow, fast := head, head              //起始条件都从head开始，慢指针步长1，快指针步长2
	for fast != nil && fast.Next != nil { //别忘了条件fast.Forward!=nil 否则fast.Next可能是空指针导致fast.Forward.Forward panic
		slow = slow.Next
		fast = fast.Next.Next
	}

	return slow
}

func generateListByVals(nums []int) *ListNode {
	var head *ListNode = nil
	for _, number := range nums {
		var p *ListNode = &ListNode{} //指针指向的位置需要初始化分配空间 C中就是malloc
		p.Val = number
		p.Next = nil
		if head != nil {
			var last *ListNode = head
			for last.Next != nil {
				last = last.Next
			}
			last.Next = p
		} else {
			head = p
		}

	}

	return head
}
